1. Background Art
Interactive residential broadband/multimedia services are expected to be the next main event in the cyberspace experience. Services like video on demand (where people will choose movies to their liking to watch at any time they choose), effective telecommuting (by bringing the full power of one's familiar office computer interface to one's home), remote learning, teleshopping, ever-increasing on-line newsgroup interactions, Web surfing, remote video game playing, and so on are waiting to jump into people's homes as soon as the 28.8 kb/s barrier of today's fastest modems is toppled tenfold or by a new breed of communication technologies.
The large excess bandwidth (well over 300 MHZ) available in today's cable TV (CATV) hybrid fiber/coaxial (HFC) plants is an ideal candidate to provide the underlying communications infrastructure for interactive digital services to the home. Cable operations that have not yet upgraded their all-coaxial plants to HFC are quickly moving in this direction.
In order to maintain compatibility with today's analog TV channels, the spectrum (of an HFC CATV plant) between 54 MHZ and 450 MHZ will not be affected by the new services. The spectrum between 5 MHZ and 42 MHZ will be used for “upstream” transmissions (i.e., from the home to the CATV headend station) and from there to the rest of the world, while the spectrum between 450 MHZ and 750 MHZ will be used for “downstream” transmissions (from the CATV headend station to the home). Since the theoretical frequency bandwidth of the cable is on the order of 1 GHZ, future generations of this technology may have a different split and different frequency ranges between upstream and downstream transmissions.
To cope better with power limitations, cost, channel error characteristics, system management, and so forth, the downstream and upstream spectra will be further subdivided into a number of channels, for example, 1-2 MHZ wide for each upstream channel, and about 6 MHZ wide for each downstream channel. Each of these channels, using appropriate modulation techniques, will be capable of carrying possibly from 2 to 10 Mb/s (or more) of digital data upstream (shared by up to a few thousand stations) and 30-40 Mb/s (or more) downstream (a broadcast channel).
Due to the “peculiarities” of the CATV tree-and-branch topology (e.g., the splitting of the receive and transmit frequencies), the various stations cannot directly listen to the upstream transmissions from other stations; hence, they are incapable of detecting collisions and ultimately coordinating their transmissions all by themselves. On the other hand, since the headend station is the focal point of the tree-and-branch topology, it can play a major role in coordinating the access to the upstream channel. In addition to coordinating upstream transmissions, since the downstream channels are broadcast (one-to-many), the headend station also has complete control of the downstream transmissions as well.
Various protocols are becoming available for controlling the transmission of upstream data and requests. Of primary interest is the formation of the IEEE 802.14 working group, which has been formed with the responsibility of standardizing the medium access control (MAC) layer protocols for HFC networks. The MAC level access protocol (MLAP) is a MAC-level protocol for the HFC environment that has been formally submitted to the IEEE 802.14 working group for consideration. MLAP is the protocol used by the present invention and is described in more detail hereinafter.
The prior art deals with management techniques and systems that control the contention between a number of devices sharing a bi-directional digital network, so that all the devices can access the shared media.
In U.S. Pat. No. 5,634,485, “Media Access Control for Digital Data,” by Buckland, et al., Buckland teaches a method for controlling the contention for use of a digital network between a broadband network headend unit and network devices. Each device contributes a portion of an upstream signal to the broadband network headend unit. The upstream signal comprises a series of frame intervals. A frame interval has two major components: request slot packets and cell slot packets. Request slot packets are allocated one for each device. There is an arbitrary number of cell slot packets. The request slot packets transmit requests for cell slots to the broadband network headend unit. The broadband network headend unit decodes the requests, determines which to grant, and responds to the requesting device with a downstream signal that identifies which cell slots are allocated to the device. Buckland teaches a protocol for use over cable TV and similar networks that is similar to the MLAP protocol used by the present invention. However, Buckland's protocol applies only to fiber-to-the-curb (FTTC) network topology and is a unique protocol that is different than the MLAP protocol used by the present invention to hybrid fiber-coaxial (HFC) networks. FTTC topology provides the fiber network much closer to each customer premise than HFC does and allows a separate coaxial cable to be run to each premise. On the other hand, the HFC topology is more standard and more difficult to deal with, since the cables are run a greater distances and each coaxial handles the traffic to and from many premises sharing the same coaxial cable. Thus, the HFC topology generates contention by all users for the use of the coaxial cable and requires a more sophisticated protocol. In addition, Buckland does not use special-purpose hardware to assist in the implementation of his protocol as the present invention does.
In U.S. Pat. No. 5,353,285, “Time Slot Management System,” by Van Der Plas et al., Van Der Plas teaches another system for controlling the sending of upstream data from various stations to a headend station. The substations send data as packets during time slots as assigned by the headend station. Part of the time slots are reserved for management information and used by the substation to inform the headend station about the bandwidth required to transfer upstream information. Accordingly, the headend station allocates time slots and informs the substations thereof. This is very similar to the request slot packets and cell slot packets taught by Buckland in U.S. Pat. No. 5,634,485 and discussed previously. Van Der Plas does not teach the MLAP approach and does not use special-purpose hardware to assist in the implementation of his protocol as does the present invention.
In U.S. Pat. No. 5,572,517, “Configurable Hybrid Medium Access Control for Cable Metropolitan Area Networks,” by Sadadi, Sadadi teaches yet another media access control (MAC) system having unique characteristics. Sadadi combines four of the popular MAC concepts into a system which is configurable to the type of communication required to support a desired service or application. The MAC system analyzes the services requested from each premise or client and determines the best MAC concept to use from four supported candidates, including plain old polling (POP) to three different versions of time division multiplexing. Sadadi does not use the MLAP format used by the present invention, nor does he use special-purpose hardware to assist in the implementation of his protocol as is done by the present invention.
In U.S. Pat. No. 5,541,921, “Isochronous Serial Time Division Multiplexer,” by Swenson et al., Swenson teaches a method and controller for filling time slots of a plurality of serial data streams by multiplexing time slots from a plurality of incoming isochronous serial data streams. Swenson uses a plurality of selectors where each selects predetermined time slots from a plurality of incoming data streams to create the plurality of outgoing serial data streams. Swenson uses a time slot method but only teaches unidirectional data flow and has no further relation to the bi-directional data flow of the present invention.
In U.S. Pat. No. 5,365,514, “Event Driven Interface for a System for Monitoring and Controlling a Data Communications Network,” by Hershey et al., Hershey teaches an apparatus for performing vector calculations. Hershey's invention receives control vectors from the system processor. The control vectors are comprised of binary patterns of 1s and 0s. Hershey's apparatus stores a plurality of control vectors and searches the data patterns on incoming serial data for the detection of identical matches between the control vectors and incoming data patterns. The matches (compare equal occurrences) are counted and generate event vectors back to the processor to inform it of the number of occurrences with respect to each control vector. Hershey's invention is used as a subsystem for monitoring and controlling data communication networks where the data communication networks are serial in nature and provide the incoming data patterns to be compared against the control vectors. Based on the occurrence of data patterns over the data communication networks, the processor can reroute data from congested networks to other optional networks. The present invention uses a vector control mechanism that is different than Hershey's in that it is a complete vector array functional unit capable of a plurality of functions including bit setting, bit resetting, bit masking, bit muxing, bit manipulation, priority encoding, and nth index generation. The present invention performs all of these functions on parallel data, never receives incoming serial data, and never looks for pattern comparisons as Hershey's invention does. The present invention does not use vectors to control network routings but instead uses vector calculations to control upstream traffic over interactive cable TV media.
In U.S. Pat. No. 5,226,079, “Non-Repudiation in Computer Networks,” by Holloway, Holloway teaches the supplementing of conventional message authentication methods by using an authentication token, known as the “Non-Repudiation Vector” (NRV). The token is used to provide very strong evidence of the origin of a electronic message. The NRV cryptographically links each message sent or received by a particular data processor on the network to create a chain of cryptographically linked messages. However, Holloway uses the term “vector” to mean a data structure comprised of a plurality of bytes, wherein the vector identifies the originator of the message, a token which binds the message to previous and subsequent messages, and an authenticator which cryptographically binds the NRV to the associated message. This is vastly different than the present invention which uses the term “bit vector” to mean a bit that represents a data structure and discloses a bit array unit for performing logical operations on the bit vectors.
In U.S. Pat. No. 5,384,777, “Adaptive Medium Access Control Scheme for Wireless LAN,” by Ahmadi et al., Ahmadi teaches yet another system for controlling the sending of upstream data from various stations to a headend station. Ahmadi's patent, however, relates to wireless radio transmissions instead of cable TV. Ahmadi's approach uses time slots and is very similar to the request slot packets and cell slot packets taught by Buckland in U.S. Pat. No. 5,634,485 and discussed previously. Ahmadi teaches a new concept of variable length time slots; however, the present invention does not use Ahmadi's wireless LAN or variable length time slots.
In U.S. Pat. No. 5,568,485, “Priority Encoder,” by Chaisemartin, Chaisemartin teaches a circular rank priority encoder that receives a plurality of requests of ranks 1 to n on each request. The encoder acknowledges the request of the lowest rank. The encoder also comprises a mask register to enable only the consideration of active ranks for each request. A mask generator provides the mask generator with a mask in which bits of the ranks 1 to x (x=1 to n) are inactive and the remaining bits are active when a request of rank x is acknowledged. The present invention incorporates a priority encoder for processing bit vectors, but it performs a different function than Chaisemartin's approach. The priority encoder of the present invention does not accept rank request but instead receives a vector comprised of y bits with each bit having a specific location within the vector and each bit being either a 1 or 0. From the vector input, the priority encoder processes the vector and returns the binary encoded number which indicates the position within the vector of the first occurrence of a logical “1”. Neither does the present invention use Chaisemartin's mask register or mask generator approaches.
It is an object of this invention to provide an efficient mechanism for subscriber tabulation of available upstream slots using an intermediate data structure associated with each upstream slot.
It is a further object of this invention to provide a compact representation of each intermediate data structure defining an upstream slot by representing each intermediate data structure with a single bit vector element.
It is a further object of this invention to provide a mechanism in the form of a bit vector array functional unit for efficient processing and selection of upstream slots using only the bit vector representation of the upstream slot data.
It is a further object of this invention to provide flexibility in the bit vector array functional unit for selecting either contention or reserved slots and for performing a plurality of pertinent calculations on the bit vector representation of the upstream slot data.